package com.mdnote.practice.double_pointer;

import org.junit.Assert;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/11/12 16:36
 * @Email rhythm_2019@163.com
 * @Description 76. 最小覆盖子串
 */
public class LeetCode76 {

    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0) {
            return "";
        }

        int left = 0, right = 0;
        int valid = 0;
        int start = 0, len = Integer.MAX_VALUE;

        Map<Character, Integer> window = new HashMap<>();
        Map<Character, Integer> need = new HashMap<>();

        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        while (right < s.length()) {
            char c1 = s.charAt(right);
            if (need.containsKey(c1)) {
                // 先加入窗口
                window.put(c1, window.getOrDefault(c1, 0) + 1);
                // 判断该字符是否数量是否满足要求
                if (window.get(c1).equals(need.get(c1))) {
                    valid++;
                }
            }
            right++;

            while (valid == need.size()) {
                // vase
                if ((right - left) < len) {
                    start = left;
                    len = right - start;
                }

                char c2 = s.charAt(left);
                if (need.containsKey(c2)) {
                    // 判断数量是否满足要求
                    if (window.get(c2).equals(need.getOrDefault(c2, 0))) {
                        valid--;
                    }
                    // 移除该字符
                    window.put(c2, window.get(c2) - 1);
                }
                left++;
            }
        }

        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

    @Test
    public void test_01() {
        LeetCode76 leetCode76 = new LeetCode76();
        Assert.assertEquals("BANC", leetCode76.minWindow("ADOBECODEBANC", "ABC"));
        Assert.assertEquals("aa", leetCode76.minWindow("aa", "aa"));
    }
}
